Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
Example 1:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 Output: 3 Explanation: The paths that sum to 8 are shown.
Example 2:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: 3
Constraints:
- The number of nodes in the tree is in the range
[0, 1000]. -109 <= Node.val <= 109-1000 <= targetSum <= 1000
Average Rating: 4.92 (159 votes)
Solution
Prefix Sum: What is it
In this article, we're going to discuss simple but powerful prefix sum technique: one pass + linear time complexity.
Prefix sum is a sum of the current value with all previous elements starting from the beginning of the structure.
It could be defined for 1D arrays (sum the current value with all the previous integers),

for 2D arrays (sum of the current value with the integers above or on the left)

or for the binary trees (sum the values of the current node
and all parent nodes),

Prefix Sum: How to Use: Number of Continuous Subarrays that Sum to Target
You might want to use the prefix sum technique for the problems like "Find a number of continuous subarrays/submatrices/tree paths that sum to target".
Before going to the current problem with the tree, let's check the idea on a simpler example Find a number of continuous subarrays that sum to target.
- Use a variable to track the current prefix sum and a hashmap "prefix sum -> how many times was it seen so far".

- Parse the input structure and count the requested subarrays/submatrices/tree paths along the way with the help of that hashmap. How to count?
There could be two situations. In situation 1, the subarray with the target sum starts from the beginning of the array. That means that the current prefix sum is equal to the target sum, and we increase the counter by 1.

In situation 2, the
subarray with the target sum starts somewhere in the middle.
That means we should add to the counter the number of times we have seen
the prefix sum curr_sum - target so far: count += h[curr_sum - target].
The logic is simple: the current prefix sum is curr_sum, and some elements
before the prefix sum was curr_sum - target. All the
elements in between sum up to curr_sum - (curr_sum - target) = target.

Solution for Number of Continuous Subarrays that Sum to Target
Here is an implementation of the solution for Find a number of continuous subarrays that sum to target.
Approach 1: Prefix Sum
Now let's reuse the same algorithm and the same code for the case of the binary tree.
There is just one thing that is particular for the binary tree. There are two ways to go forward - to the left and to the right. To keep parent->child direction, we shouldn't blend prefix sums from the left and right subtrees in one hashmap.
Algorithm
-
Let's initialize tree paths counter
count = 0, and the hashmaph"prefix sum -> how many times was it seen so far". -
One could parse the tree using recursive preorder traversal: node -> left -> right:
preorder(node: TreeNode, curr_sum: int) -> None. This function takes two arguments: a tree node and a prefix sum before that node. To start the recursion chain, one should callpreorder(root, 0).-
The first thing is to update the current prefix sum by adding the value of the current node:
curr_sum += node.val. -
Now one could update the counter. One should consider two situations.
In situation 1, the tree path with the target sum starts from the root. That means the current prefix sum is equal to the target sum
curr_sum == k, so one should increase the counter by 1:count += 1.In situation 2, the tree path with the target sum starts somewhere downwards. That means we should add to the counter the number of times we have seen the prefix sum
curr_sum - targetso far:count += h[curr_sum - target].The logic is simple: the current prefix sum is
curr_sum, and several elements before the prefix sum wascurr_sum - target. All the elements in between sum up tocurr_sum - (curr_sum - target) = target. -
Now it's time to update the hashmap:
h[curr_sum] += 1. -
Let's parse left and right subtrees:
preorder(node.left, curr_sum),preorder(node.right, curr_sum). -
Now the current subtree is processed. It's time to remove the current prefix sum from the hashmap, in order not to blend the parallel subtrees:
h[curr_sum] -= 1.
-
-
Now the preorder traversal is done, and the counter is updated. Return it.

Implementation
On the following example the target sum is equal to 8.
Complexity Analysis
-
Time complexity: O(N), where N is a number of nodes. During preorder traversal, each node is visited once.
-
Space complexity: up to O(N) to keep the hashmap of prefix sums, where N is a number of nodes.
This is the best editorial i've ever seen. Very well elaborated and correlated with other pre-existing problems.
August 7, 2020 1:58 AM
I took me a while to appreciate this solution, especially the part "currSum - k".
July 21, 2020 8:10 PM
beautiful article, thank you
Took me a little while to think through why h[curr_sum] += 1 has to come after count += h[curr_sum - k]. Think about an edge case when sum equals to 0.
Why do we use globals in leetcode, my understanding was globals are not liked by interviewers.
August 8, 2020 8:21 PM
Thanks for the write-up. I learned a lot!!
nice write up...learned a lot!
Can someone confirm something?
# remove the current sum from the hashmap
# in order not to use it during
# the parallel subtree processing
h[curr_sum] -= 1
when the code bottoms out (reaches an end leaf/node) on the recursive calls, the two preorder calls return nothing, then it proceeds to h[curr_sum] -= 1 when then removes that node value from the hashmap, correct?
August 9, 2020 2:36 AM
Great explanation; very much enjoying reading it! Thank you.
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 08/08/2020 12:54 | Accepted | 24 ms | 15.6 MB | cpp |
xxxxxxxxxx/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: int pathSum(TreeNode* root, int targetSum) { }};